不会真的有人在考了 次后还不会一个算法吧 不会吧不会吧
老早就学了这玩意,但是几次考试板子也写不对。于是近期重新梳理了一下算法。
算法流程
浅い夢だから 胸をはなれない
给定一张 n 个点 m 条边的无向图。当你在点 u 时,你可以花费 1 的费用向系统询问当前可以去哪个点,系统会从点 u 的所有出边中随机选择一条告诉你。你可以选择去,或者重新花费并询问。初始时刻你在 1 号点,要去 n 号点。求最少花费的期望。
1≤n,m≤3×105
Fibonacci 数列的性质很多,有的常考,有的不常考。
这些性质都有可能是解题关键。这里稍作总结。
Fibonacci 的定义很多,本文采取如下的递归定义:
给你 n 种颜色的球,每个球有 k 个,把这 n×k 个球排成一排,把每一种颜色的最左边出现的球涂成白色(初始球不包含白色),求最终有多少种不同的颜色序列,答案对 109+7 取模。
1≤n,k≤2×103
给定一张 n 个点 m 条边的图,一条边 (u,v) 有 31 的概率消失,31 的概率定向成 u→v ,31 的概率定向成 v→u 。求最后的图是 DAG 的概率。
n≤20,m≤2n(n−1)